package com.ai.zuochengyun.phase01.class07;

/**
 * 汉诺塔问题
 */
public class Code02_Hanoi {

    public static void main(String[] args) {
        hanoi1(3);
        System.out.println("------------------");
        hanoi2(3);
    }

    /**
     * 解法1
     */
    public static void hanoi1(int level) {
        // 运用6种组合
        // 抽象成三步
        // 1、假定第二层到第n层是一个整体，移动到中间
        // 2、然后最底层的移到最右侧
        // 3、然后中间的移动到右侧
        leftToRight(level);
    }

    /**
     * 左 -> 右
     * @param level
     */
    private static void leftToRight(int level) {
        if (level == 1) {
            System.out.println("move 1 from left to right");
            return;
        }

        // 不为1的时候，需要中间进行中转
        leftToMid(level - 1);
        System.out.println("move "+level+" from left to right");
        midToRight(level-1);
    }

    /**
     * 左 -> 中
     * @param level
     */
    private static void leftToMid(int level) {
        if (level == 1) {
            System.out.println("move 1 from left to mid");
            return;
        }

        // 不为1的时候，需要中间进行中转
        leftToRight(level - 1);
        System.out.println("move "+level+" from left to mid");
        rightToMid(level-1);
    }

    /**
     * 中 -> 右
     * @param level
     */
    private static void midToRight(int level) {
        if (level == 1) {
            System.out.println("move 1 from mid to right");
            return;
        }

        // 不为1的时候，需要中间进行中转
        midToLeft(level - 1);
        System.out.println("move "+level+" from mid to right");
        leftToRight(level-1);
    }

    /**
     * 中 -> 左
     * @param level
     */
    private static void midToLeft(int level) {
        if (level == 1) {
            System.out.println("move 1 from mid to left");
            return;
        }

        // 不为1的时候，需要中间进行中转
        midToRight(level - 1);
        System.out.println("move "+level+" from mid to left");
        rightToLeft(level-1);
    }

    /**
     * 右 -> 中
     * @param level
     */
    private static void rightToMid(int level) {
        if (level == 1) {
            System.out.println("move 1 from right to mid");
            return;
        }

        // 不为1的时候，需要中间进行中转
        rightToLeft(level - 1);
        System.out.println("move "+level+" from right to mid");
        leftToMid(level-1);
    }

    /**
     * 右 -> 左
     * @param level
     */
    private static void rightToLeft(int level) {
        if (level == 1) {
            System.out.println("move 1 from right to left");
            return;
        }

        // 不为1的时候，需要中间进行中转
        rightToMid(level - 1);
        System.out.println("move "+level+" from right to left");
        midToLeft(level-1);
    }


    /**
     * 解法1
     */
    public static void hanoi2(int level) {
        if (level > 0) {
            leftToRight(level, "left", "right", "mid");
        }
    }

    /**
     * 运用6种组合
     * 抽象成三步
     * 1、第二层到第n层是一个整体，从原始位置移动到中转点
     * 2、然后第一层移动到目标位置
     * 3、然后第二层到第n层从中转点移动到目标位置
     * @param level
     * @param from
     * @param to
     * @param other
     */
    private static void leftToRight(int level, String from, String to, String other) {
        // 第一层移动到目标位置
        if (level == 1) {
            System.out.println("move 1 from "+from+" to "+to);
            return;
        }

        // 第二层到第n层是一个整体，从原始位置移动到中转点
        leftToRight(level -1, from, other, to);
        System.out.println("move "+level+" from "+from+" to "+to);
        // 第二层到第n层是一个整体，从中转点移动到目标位置
        leftToRight(level -1, other, to, from);
    }

}
